Petit théorème de Fermat (forme forte)

Petit théorème de Fermat (forme forte)

Si $p\in \mathcal{P}$ , alors pour tout $n\in \mathbb{Z}$ tel que $p$ ne divise pas $n$ , on a :  $n^{p-1}\equiv 1[p]$ .

Démonstration

Soit $p\in \mathcal{P}$ et $n\in \mathbb{Z}$ tel   que $p$ ne divise pas $n$ .
On considère les nombres $n$ , $2n$ , $3n$ , ..., $(p-1)n$ , c'est-à-dire $kn$ pour $k\in \{1;...;p-1\}$ .

Pour tout $k\in \{1;...;p-1\}$ , on note $r_k$ le reste dans la division euclidienne de $kn$ par $p$ ,
c'est-à-dire  $kn=p{q}_k+r_k$  avec  $q_k\in \mathbb{Z}$  et  \(0 \leqslant r_k.

Observation 1 : pour tout $k\in \{1;...;p-1\}$ , on a $r_k\in \{1;...;p-1\}$ .
En effet, soit $k\in \{1;...;p-1\}$ . On sait déjà que $r_k\in \{0;...;p-1\}$ .
De plus, $p$ ne divise pas $k$ (car \(0) et $p$ ne divise pas $n$ , donc $p$ ne divise pas $kn$ .
Or $kn=p{q}_k+r_k$ , donc $r_k\ne 0$ .

Observation 2 : pour tous $k$ , $k^{\prime }\in \{1;...;p-1\}$ , si $k\ne k^{\prime }$ , alors $r_k\ne r_{k^{\prime }}$ .
En effet, soit $k$ , $k^{\prime }\in \{1;...;p-1\}$ tels que \(k.
Ainsi, $k^{\prime }-k\in \{1;...;p-1\}$ .
Par suite, $p$ ne divise pas $k^{\prime }-k$ et $p$ ne divise pas $n$ , donc $p$ ne divise pas  $n(k^{\prime }-k)=n{k}^{\prime }-nk=p{q}_{k^{\prime }}+r_{k^{\prime }}-(p{q}_k+r_k)=p(q_{k^{\prime }}-q_k)+r_{k^{\prime }}-r_k$  
et donc $r_{k^{\prime }}-r_k\ne 0$ , c'est-à-dire $r_k\ne r_{k^{\prime }}$ .

D'après les deux observations précédentes, l'ensemble $\{r_1;r_2;...;r_{p-1}\}$ est formé de $(p-1)$ entiers tous distincts, et cet ensemble est inclus dans  $\{1;...;p-1\}$ .
Par conséquent, cet ensemble est exactement $\{1;...;p-1\}$ (dans un ordre quelconque).

On en déduit que  $r_1{r}_2...r_{p-1}=1\times 2\times ...\times (p-1)=(p-1)!$ .

Pour tout $k\in \{1;...;p-1\}$ , on a $kn=p{q}_k+r_k$ donc $kn\equiv r_k[p]$ .

Par produit,
$\begin{array}{rl}1n\times 2n\times ...\times (p-1)n\equiv r_1{r}_2...r_{p-1}[p]& ⟺(p-1)!n^{p-1}\equiv (p-1)![p]\\ & ⟺(p-1)!(n^{p-1}-1)\equiv 0[p]\end{array}$  
donc $p$ divise $(p-1)!(n^{p-1}-1)$ .

Comme $p$ et $(p-1)!$ sont premiers entre eux, on en déduit grâce au théorème de Gauss que $p$ divise $n^{p-1}-1$ , c'est-à-dire $n^{p-1}-1\equiv 0[p]$ , et donc $n^{p-1}\equiv 1[p]$ .